Amy Okamoto

MATH300 Geometry

 

Finite Power Sets

 

To prove that no finite set can be in one-to-one correspondence with its power set, we need to show that any finite set A cannot be in one-to-one correspondence with its power set P(A).

The power set P(A) is the collection of all subsets of A. Therefore, P(A) includes A itself, and P(A) also includes the empty set { }.

 

EXAMPLE: Let A = {amy}. Then P(A) = { {amy}, { } }.

The set A contains one element. Its power set P(A) contains two elements.

 

EXAMPLE: Let A = { }. Then P(A) = { { } }.

The set A contains no elements. Its power set P(A) contains one element.

 

Let x be any element of P(A). Since P(A) only contains subsets of A, that must mean x is a subset of A. Then every element of x is also an element of A, by the definition of a subset.

 

EXAMPLE: Let P(A) be all the possible combinations of cartoons that I can watch

between 3:00 and 4:00. So P(A) = { {Animaniacs}, {Batman}, {Animaniacs, Batman}, { } }. The elements of P(A) are subsets of A by definition, so A is all cartoons available between 3:00 and 4:00. We can say that A = {Animaniacs, Batman}. Elements of A are Animaniacs and Batman.

For our x, we pick any element of P(A). Our possibilities are {Animaniacs}, {Batman}, {Animaniacs, Batman}, and { }. Elements of x are Animaniacs or Batman. This means that an element of x can be either Animaniacs, Batman, or Animaniacs and Batman.

 

 

Let’s look at the elements of the set A = { a, b, c, . . . }.

 

EXAMPLE: Let A = { a, b, c, . . . }. Then P(A) = { { }, {a}, {b}, . . . , {a, b}, {a,c}, . . .}.

 

Elements of A Elements of P(A)

 

a

 

{a}

 

b

 

{b}

 

.

.

.

 

.

.

.

 

 

 

{a, b}

 

 

 

{a, c}

 

 

 

.

.

{b, c}

.

.

{a, b, c}

.

.

{a, b, c, . . .}

 

 

 

{ }

 

We can see in the above example that for any finite set A, P(A) will have at least one more element than A (the empty set). The set A and P(A) therefore cannot be in one-to-one correspondence with each other.

We can also say that for any A with n number of elements, P(A) will have 2n elements (Kolen). For any set A with n elements and its power set P(A) with m elements, m = 2n > n. P(A) always has more elements than A. This statement is true even for n = 0. As we noted in Example 2, when n = 0, m = 1 = 20.

 

REFERENCES

J. Kolen, Theory of Computations: Power Set, http://www.coginst.uwf.edu/~hlarriso/ TOC/node14.html, 1998.

 

A.A. Fraenkel, Y. Bar Hillel, and A. Levy, Foundations of Set Theory, 2nd edition, Elsevier Science Publisheres B. V., Amsterdam, Netherlands, 1984.